package 系统复习.贪心算法;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 */
public class L1005 {

    public int largestSumAfterKNegations(int[] nums, int k) {

        Arrays.sort(nums);
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            } else {
               break;
            }
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (k % 2 == 1) {
                nums[i] = -nums[i];
                break;
            }
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        return sum;
    }

    public static void main(String[] args) {
        L1005 l1005 = new L1005();
        System.out.println(l1005.largestSumAfterKNegations(new int[]{-8,3,-5,-3,-5,-2}, 6));
    }
}
